package com.example.algorithm.service.impl;

import com.example.algorithm.service.HashService;
import org.springframework.stereotype.Service;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @auth Administrator
 * @create @2024/7/20@9:28
 * @decription
 * 哈希表解法：
 * 1解题思路
 * 1).用 hashMap 存储遍历过的元素和对应的索引。
 * 2).每遍历一个元素，看看 hashMap 中是否存在满足要求的目标数字。
 * 3).所有事情在一次遍历中完成（用了空间换取时间）。
 * 2复杂度分析
 *1)时间复杂度：O(N)
 *2)空间复杂度：O(N)
 **/
@Service
public class HashServiceImpl implements HashService {

    /**
     *
     *NO.1 两数之和
     *
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     *
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     * 解法一：暴力枚举
     * 解法二：哈希表
     *
     *
     *
     * @param nums
     * @param target
     * @return
     */
    @Override
    public int[] twoSum(int[] nums, int target) {

        Map<Integer ,Integer> temp = new HashMap();
        for(int i=0;i<nums.length;i++){
            int release = target- nums[i];
            if(temp.containsKey(release)){
                return new int[] {temp.get(release),i,};
            }else{
                temp.put(nums[i],i);
            }

        }
        return new int[0];

    }

    /**
     * NO.2字母异位词分组
     *
     * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
     *
     * 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
     *  解法一：哈希表排序法
     *  解法二：哈希表计数法
     *  解法三：stream的groupingBy 计算法
     *
     * @param strs
     * @return
     */

    @Override
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> res = new HashMap<>();
        for(String str :strs){
            char arr[] = str.toCharArray();
            Arrays.sort(arr);
            res.computeIfAbsent(String.valueOf(arr),key->new ArrayList<>()).add(str);
        }

        return res.values().stream().collect(Collectors.toList());
    }

    /**
     *NO.3最长连续队列
     * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
     *
     * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
     * 解法一：哈希表
     * 解法二：动态规划
     * 解法三：并查集
     * 解法四：双指针
     *
     *
     * @param nums
     * @return
     */
    @Override
    public int longestConsecutive(int[] nums) {
        /**
         * 去重
         */
        HashSet<Integer> temp = new HashSet<>();
        // 建立一个存储所有数的哈希表，同时起到去重功能
        for(int num :nums){
            temp.add(num);
        }
        int maxLenth=0;
        // 遍历去重后的所有数字
        for(int num :temp){
            // 只有当num-1不存在时，才开始向后遍历num+1，num+2，num+3......
            if(!temp.contains(num-1)){
                int length = 1;
                int cur = num;
                while (temp.contains(cur+1)){
                    length=length+1;
                    cur = cur +1;
                }
                // [num, cur]之间是连续的，数字有cur - num + 1个
                maxLenth= Math.max(maxLenth,length);
            }


        }
        return maxLenth;
    }
}
